/**
 * 从中序遍历和后续遍历序列构造二叉树
 *
 * 给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
 *
 * 示例 1:
 * 输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
 * 输出：[3,9,20,null,null,15,7]
 *
 * 示例 2:
 * 输入：inorder = [-1], postorder = [-1]
 * 输出：[-1]
 *
 * 提示:
 * 1 <= inorder.length <= 3000
 * postorder.length == inorder.length
 * -3000 <= inorder[i], postorder[i] <= 3000
 * inorder 和 postorder 都由 不同 的值组成
 * postorder 中每一个值都在 inorder 中
 * inorder 保证是树的中序遍历
 * postorder 保证是树的后序遍历
 */

/**
 * 这一题和 105 题一样的思路
 * 只不过是反了过来, 先从右子树开始
 * 时间复杂度 : O(n ^ 2)
 * 空间复杂度 : O(n)
 */

public class Main {

    // 使用一个数记录我们前序遍历使用到哪个数了
    public int target;

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        target = postorder.length - 1;
        // 递归函数, 这里我们要处理的是中序遍历, 所以用中序遍历
        return buildTree(postorder, inorder, 0, inorder.length - 1);
    }

    public TreeNode buildTree(int[] postorder, int[] inorder, int start, int end) {

        // 区间不符合要求, 返回 null
        if (start > end) {
            return null;
        }

        // 构造根节点
        TreeNode root = new TreeNode(postorder[target]);

        // 根节点在中序遍历中的位置
        int cur = findNum(inorder, postorder[target], start, end);

        // 每使用一次, 目标位置就要加 1
        target--;

        // 右子树是右边构成的
        root.right = buildTree(postorder, inorder, cur + 1, end);

        // 左子树是左边构成的
        root.left = buildTree(postorder, inorder, start, cur - 1);

        // 返回根节点
        return root;
    }

    // 在中序遍历中寻找目标数的位置
    // 可以使用 hash 优化时间复杂度
    public int findNum(int[] inorder, int num, int start, int end) {

        for (int i = start; i <= end; i++) {
            if (inorder[i] == num) {
                return i;
            }
        }

        // 找不到就返回 -1, 肯定是能找到的, 这里是为了照顾编译器
        return -1;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}